ABC171 F

https://gyazo.com/06a507356d75cd4cd98f157068093c3d

コンテスト中の思考

残り45分

短い文字列の場合を調べて規則性を見出してからDPだろう

よーし、具体的な文字列の内容と関係なく、長さNで文字種Kの文字列に1文字追加すると、以下の関係が成り立つ！

f(N+1, K+1) = (26 - K) * (N + 1) * f(N, K)

f(N+1, K) = ((K - 1) * (N + 1) + 1) * f(N, K)

DPしよう

合流が起きるぞ

マスを四角く並べて隅から順に塗りつぶす…

あれ、これ100万×100万のオーダーでは？？

この時点で残り15分

実際に短い文字列に対してプログラムで全パターン列挙して数えるのをやらせて、パターンを発見しようとしているうちに時間切れ

解説を読んでからコンテスト後

https://gyazo.com/be0eaeaa0e90dfe8e3bdf686981650c9

文字列の先頭に文字を挿入することを考えると25倍

先頭文字と同じものを挿入するのは、2文字目に挿入するのと区別がつかないからカウントしてはいけない

よって26文字から1文字引いて25

この挿入の後に、さらに前に文字を挿入してはいけない

それは挿入順を入れ替えたものと区別がつかないから

一般に、挿入した文字の挿入タイミングを入れ替えたものは同一なので、順列ではなく組み合わせになる必要がある

重複ありなのでcombinations with replacement(日本語でなんというのかは忘れた)

https://gyazo.com/36611c3416e86632e0db04d9961c5019

カーソルの位置をN、追加する文字数をKとした時に、追加するか、カーソルを進めるか、の二択を繰り返していって0,0になればゴール

よく見たら途中の道はどこを通っても25倍なので、右下の26倍の道に入るタイミングで場合わけしたらよさそう

https://gyazo.com/4e7c83ae3b8aa3aa16ce4c2a044b885c

最初から26倍の道に入るのは1通り

1個25を取ってからから入るのはN-1通り

図では2通り

(とこの時点では考えたが、長さNの文字列に対する挿入ポイントはN+1あるので本当はN通り、伏線A)

2個25を取るのは、重複ありで2個選ぶコンビネーション

図では3通り

というわけで求める値は

$ \sum_{i=0}^K 25^i 26^{K-i} C^R(N-1, i)

早速計算してみるが、サンプル1の答えが合わない

NやKをひとつずらして試してみたらNをひとつ増やした時に正解になることがわかったのでそれでいいやということにした(おいおい

$ \sum_{i=0}^K 25^i 26^{K-i} C^R(N, i)

この解説を書いてる時に理由がわかったので結果オーライ、伏線A回収

サンプル1に正解するコード

code:python

K = 5

S = "oof"

P = 10 ** 9 + 7

N = len(S)

def factorial(n):

ret = 1

for i in range(2, n + 1):

ret *= i

return ret

def comb_rep(n, r):

return factorial(n + r - 1) // factorial(r) // factorial(n - 1)

ret = 0

for i in range(K + 1):

ret += (

(25 ** i) *

(26 ** (K - i)) *

comb_rep(N, i)

)

print(ret)

そのままサンプル2を入力してみたら時間がかかる

そりゃそうでしょうね、剰余を取ってないのですごく桁の大きい長整数演算してるのだろう

サンプル2が十分な速度で計算できるようになったがなぜか答えが違う…

剰余を取ってから加減算と乗算をするのは許されるけどコンビネーションの中でやってる整除は許されない

なるほど逆元を求めておけば乗算で割り算ができるわけか

inv[a] = MOD - inv[MOD % a] * (MOD / i) % MOD;

この式を使えばO(1)で逆元求まるのでO(N)で逆元テーブルが作れる

漸化式の導出はちゃんと考えてない

とりあえずこれを使うことでサンプル2は正解できた

code:python

f = 1

invf = 1

for i in range(2, N + K):

f *= i

f %= P

q, r = divmod(P, i)

invf %= P

サブミットしてみたらTLEだった

手元での速度比較

code::

pure python

real 0m2.910s

user 0m2.781s

sys 0m0.124s

compiled with numba

real 0m0.363s

user 0m0.683s

sys 0m0.139s

numbaでどれくらい速くなるのか測ってみたのだが、userがrealを超えてるな…なにも考えてないPythonのコードがマルチスレッド(GIL OFF)で走るということ？？